The present invention relates to circuit or system simulators and synthesis systems, and more particularly, to an improved method for finding elementary loops in a graph representing a circuit or system.
One step in the analysis of a circuit or system involves the generation of a directed graph that represents the circuit. Consider the class of systems that can be described graphically by a block diagram in which each element of the system can be represented by a block and the connection between two elements can be represented by a line. Electronic circuits or systems fall into this class of systems. In order to analyze the system topology, the system block diagram can be mapped to a graph consisting of a plurality of vertices connected by xe2x80x9cedgesxe2x80x9d. Each vertex corresponds to one of the blocks in the block diagram, each edge in the graph corresponds to a connection between the blocks.
Many circuit simulation and synthesis problems require that all of the elementary loops (circuits or cycles) of the directed graph representing the circuit be located. A directed graph is a graph in which the edges specify a direction. In the case of a circuit, the direction represents the direction in which signals travel from one element (block) to the adjacent element. For example, to schedule a hierarchical communication system all of the feed back loops in the system must be found. One method for solving high-level DSP synthesis problems requires that all loops in a directed graph must be located.
Prior art methods for locating the loops in a directed graph are computationally to expensive to be applied to many problems of interest. For example, Taian""s method (R. Tajan, xe2x80x9cDepth-First Search and Linear Graph Algorithmxe2x80x9d, SIAM J. Comput. Vol.1, No.2, June, 1972 for more details) requires a time that is proportional to (C+1)(VE), where V is the number of vertices in the graph, E is the number of edges, and C is the number of loops in the graph. In the worst case, C approaches E, and V is of order E. Hence the computational work load can be of order V3. This workload is unacceptable for many practical applications.
Broadly, it is the object of the present invention to provide an improved method for finding the elementary loops of a directed graph representing a circuit.
It is a further object of the present invention to provide a method for finding the elementary loops of a graph which imposes a lower computational workload then prior art methods.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.
The present invention is a method for operating a computer to find elementary loops in a strongly connected component of a graph. In the basic method, the computer identifies a starting vertex from the vertices of the strongly connected component. The potential vertices are those that have not been examined as a possible starting vertex for an elementary loop and which are not contained in any elementary loop discovered thus far. The vertices of the strongly connected component are then searched for a path starting and ending on the identified vertex. If the search finds a path starting and ending of the identified vertex, the path is recorded as an elementary loop. This process is repeated until no starting vertex can be identified. To improve the efficiency of the search process, the computer identifies vertices that are the starting vertex for paths that are shared by more than one elementary loop. The shared paths are stored separately and used to avoid searching the vertices of the path more than once.